package com.lijing.Merge;

public class Merge {
    private static Comparable[] assist;
    public Merge() {
    }

    /**
     * 对数组中的所有元素进行排序
     * @param arr 数组
     */
    public static void sort(Comparable[] arr){
        assist = new Comparable[arr.length];
        int lo = 0;
        int hi = arr.length-1;
        sort(arr,lo,hi);
    }


    /**
     * 对数组中从索引lo到hi的元素进行排序
     * @param arr 数组
     * @param lo 左索引lo
     * @param hi 右索引hi
     */
    private static void sort(Comparable[] arr, int lo, int hi){

        if (hi<=lo){
            return;
        }
        int mid = lo+(hi-lo)/2;
        sort(arr,lo,mid);
        sort(arr,mid+1,hi);
        merge(arr,lo,mid,hi);
    }

    /**
     * 归并，左子数组：lo-->mid,右子数组：mid+1-->hi
     * @param arr 数组
     * @param lo 左索引
     * @param mid 中间位置
     * @param hi 右索引
     */
    private static void merge(Comparable[] arr, int lo, int mid, int hi){
        //1.设置3个指针，分别指向中间数组index，左子数组p1、右子数组p2
        int index = lo;
        int p1 = lo;
        int p2 = mid+1;
        //2.遍历比较左子数组和右子数组，将结果按大小顺序放置在assist中
        while(p1<=mid && p2<=hi){//有任意一个指针越界就暂停
            if(less(arr[p1],arr[p2])){//p1指向的元素小于p2指向的元素，将p1指向元素赋值给assist
                assist[index++]=arr[p1++];
            }else{
                assist[index++]=arr[p2++];
            }
        }
        //3.查看是否还有未遍历完的p1,p2，将剩下的进行填充
        while(p1<=mid){
            assist[index++]=arr[p1++];
        }
        while(p2<=hi){
            assist[index++]=arr[p2++];
        }
        //4.将assist数组的元素复制到arr中
        for (int i = lo; i <= hi; i++) {
            arr[i] = assist[i];
        }

    }

    /**
     * 比较v,w的大小
     * @param v v
     * @param w w
     * @return v<w返回true
     */
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

    /**
     * 交换元素
     * @param arr 数组
     * @param i i
     * @param j j
     */
    private static void exch(Comparable[] arr, int i, int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
